[LeetCode] 204 - Count Primes

題意

輸出小於n的質數有幾個。

解法

質數的演算法有許多種，這邊選擇Sieve of Eratosthenes。

心得

不知道測資範圍及如何檢驗，所以乾脆每次都重新建表。

程式

class Solution {
public:
	int countPrimes(int n) {
		int prime_count = 0 ;
		bool prime[n] ;
		for ( int i = 2 ; i < n ; i ++ ){
			prime[i] = true ;
		}
		prime[0] = prime[1] = false ;
		for ( int i = 2 ; i < n ; i ++ ){
			if ( prime[i] == true ){
				prime_count ++ ;
				for ( int j = i + i ; j < n ; j += i )
					prime[j] = false ;
			}
		}
		return prime_count ;
	}
};